package com.itheima.leetcode.od.b.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * (B卷,100分)- AI面板识别（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。
 * <p>
 * 由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，
 * <p>
 * 请输出先行后列排序的指示灯的编号，排序规则：
 * <p>
 * 每次在尚未排序的灯中挑选最高的灯作为的基准灯，
 * <p>
 * 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。
 * <p>
 * 输入描述
 * <p>
 * 第一行为N，表示灯的个数
 * <p>
 * 接下来N行，每行为1个灯的坐标信息，格式为：
 * <p>
 * 编号 x1 y1 x2 y2
 * <p>
 * 编号全局唯一
 * <p>
 * 1 ≤ 编号 ≤ 100
 * <p>
 * 0 ≤ x1 < x2 ≤ 1000
 * <p>
 * 0  ≤  y1 < y2 ≤ 1000
 * <p>
 * 输出描述
 * <p>
 * 排序后的编号列表，编号之间以空格分隔
 * <p>
 * 用例
 * <p>
 * 输入	5
 * <p>
 * 1 0 0 2 2
 * <p>
 * 2 6 1 8 3
 * <p>
 * 3 3 2 5 4
 * <p>
 * 5 5 4 7 6
 * <p>
 * 4 0 4 2 6
 * <p>
 * 输出	1 2 3 4 5
 * <p>
 * 说明
 */
public class AIPanelRecognition {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Light[] lights = new Light[n];
        for (int i = 0; i < n; i++) {
            int id = sc.nextInt();
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            lights[i] = new Light(id, (x1 + x2) / 2, (y1 + y2) / 2, (x2 - x1) / 2);
        }*/

        int n = 5;
        String input = "1 0 0 2 2\n2 6 1 8 3\n3 3 2 5 4\n5 5 4 7 6\n4 0 4 2 6";
        Light[] lights = Arrays.stream(input.split("\n"))
                .map(s -> {
                    int[] arr = Arrays.stream(s.split(" "))
                            .mapToInt(Integer::parseInt).toArray();
                    return new Light(arr[0],
                            (arr[1] + arr[3]) / 2,
                            (arr[2] + arr[4]) / 2,
                            (arr[4] - arr[2]) / 2);
                })
                .toArray(Light[]::new);

        System.out.println(getResult(lights));
    }

    public static String getResult(Light[] lights) {
        // 按照圆心y坐标升序
        Arrays.sort(lights, (a, b) -> a.y - b.y);

        // sameRowLights记录同一行的灯
        ArrayList<Light> sameRowLights = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        Light base = lights[0];
        sameRowLights.add(base);

        for (int i = 1; i < lights.length; i++) {
            Light light = lights[i];

            // 如果lights[i]的纵坐标和base的纵坐标相差不超过半径，则视为同一行
            if (light.y - base.y <= base.r) {
                sameRowLights.add(light);
            } else {
                // 否则，不是同一行
                // 针对同一行的灯，再按照横坐标升序
                ans.addAll(sameRowLights.stream()
                        .sorted((a, b) -> a.x - b.x)
                        .map(a -> a.id)
                        .collect(Collectors.toList()));
                sameRowLights.clear();

                // 开始新的一行记录
                base = light;
                sameRowLights.add(base);
            }
        }

        // 收尾操作，注意不要漏了最后一行
        ans.addAll(sameRowLights.stream()
                .sorted((a, b) -> a.x - b.x)
                .map(a -> a.id)
                .collect(Collectors.toList()));

        return ans.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }
}

class Light {
    int id; // 编号
    int x; // 圆心横坐标
    int y; // 圆心纵坐标
    int r; // 圆半径

    public Light(int id, int x, int y, int r) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.r = r;
    }
}